package hot100;


/*
 * Author：江松
 * Date：2023/4/8 14:01
 *
 回文子串:
 1,遍历，分为2中情况，中心为1个点和中心为2个点   O(n^2)
 2,Manacher 算法
 */

public class Main647 {

    public int countSubstrings(String s) {
        int n=s.length();
        int res=0;
        for(int i=0;i<n;++i){
            //讨论中心为1,2点时
            for(int j=0;j<2;++j){
                int l=i;
                int r=i+j;
                while(l>=0&&r<n&&s.charAt(l--)==s.charAt(r++))res++;
            }
        }
        return res;
    }



    /*
    //错误的，老是重复和遗漏
    public int countSubstrings(String s) {
        int res=0;
        int last=-1;
        for(int i=0;i<s.length();++i){
            char ch=s.charAt(i);
            res++;

            //向左扩散，不用向右扩散，因为后面的向左包括前面向右
            //注意向左扩散的可能和中间扩散的重复
            int ll=i-1;
            while(ll>last&&ll>=0&&s.charAt(ll)==s.charAt(i)){
                ll--;
                res++;
            }
            //中间扩散
            int l=i-1,r=i+1;
            while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
                last=l;
                res++;
                l--;
                r++;
            }
        }
        return res;
    }
    */
}
